import java.util.Arrays;

class Heap{
   public int[] elem;
   public int useSize;

    public Heap() {
        this.elem =new int[10];
    }
    public void inti(int[]array){
        for (int i = 0; i < array.length; i++) {
            elem[i]=array[i];
            useSize++;
        }
    }
    private void swap(int[]array,int x,int y){
        int tmp=array[x];
        array[x]=array[y];
        array[y]=tmp;
    }
    public void siftDown(int parent,int end){
        int child=parent*2+1;
        while (child<=end) {
            if (child + 1 <= end && elem[child] < elem[child + 1]) {
                child++;
            }
            if (elem[child] > elem[parent]) {
                swap(elem, parent, child);
            } else {
                break;
            }
            parent=child;
            child=parent*2+1;
        }
    }
    public void createHeap(){
        for (int parent = (useSize-1-1)/2; parent >=0; parent--) {
            siftDown(parent,useSize-1);
        }
    }
    private boolean isFull(){
        return useSize==elem.length;
    }
    private void siftUp(int child){
        if (useSize==1){
            return;
        }
        int parent=(child-1)/2;
        while (parent>=0){
            if (elem[child]>elem[parent]){
                swap(elem,child,parent);
            }else {
                break;
            }
            child=parent;
            parent=(child-1)/2;
        }
    }
    public void offer(int val){
        if(isFull()){
            elem=Arrays.copyOf(elem,elem.length*2);
        }
        elem[useSize]=val;
        useSize++;
        siftUp(useSize-1);
    }
    private boolean isEmpty(){
        return useSize==0;
    }
    //队列，删除首元素
    private void isIndexLegal()throws IndexException{
            throw new IndexException("队列为空");
    }
    public int poll(){
        try {
            if (isEmpty()){
                isIndexLegal();
            }
        }catch (Exception e){
            e.printStackTrace();
        }
        int old=elem[0];
        swap(elem,0,useSize-1);
        useSize--;
        siftDown(0,useSize-1);
        return old;
    }
    public void sort(){
        while (useSize>1) {
            swap(elem, 0, useSize - 1);
            useSize--;
            siftDown(0, useSize - 1);
        }
    }

    @Override
    public String toString() {
        return "elem=" + Arrays.toString(elem) +
                "   "+"useSize: "+useSize;
    }
}
public class Test {
    public static void main(String[] args) {
        int[] array={12,3,5,17,8,4,26,0,13,-1};
        Heap heap=new Heap();
        heap.inti(array);
        heap.createHeap();
        System.out.println(heap.toString());
        Heap heap1=new Heap();
        heap1.offer(12);
        heap1.offer(3);
        heap1.offer(5);
        heap1.offer(17);
        heap1.offer(8);
        heap1.offer(4);
        heap1.offer(26);
        heap1.offer(0);
        heap1.offer(13);
        heap1.offer(-1);
        System.out.println(heap1.toString());
        heap1.poll();
        System.out.println(heap1.toString());
        heap1.sort();
        System.out.println(heap1.toString());





    }
}
